package a09_贪心算法;

import java.util.Arrays;

/**
 * <p>
 * a17_用最少数量的箭引爆气球
 * </p>
 *
 * @author flyduck
 * @since 2025/1/15
 */
public class a17_用最少数量的箭引爆气球 {
    public static void main(String[] args) {
        int[][] points = new int[][]{{-2147483646,-2147483645},{2147483646,2147483647}};
        int result = points[0][0] - points[1][0];
        int minArrowShots = findMinArrowShots(points);
    }
    //重叠的气球尽量放在一起，用一只箭射掉
    //先按照左边界进行排序
    //如果i的左边界 > i-1的右边界，不会重叠，需要再有一个弓箭去射
    //如果i的左边界 <= i-1的右边界，更新右边界 = Math.min(i的右边界,i-1的右边界)
    public static int findMinArrowShots(int[][] points) {
        points = Arrays
                .stream(points)
                .sorted((item1,item2) -> {
                    long result = (long)item1[0] - (long)item2[0];
                    if (result > 0) {
                        return 1;
                    }else if(result == 0){
                        return 0;
                    }else {
                        return -1;
                    }
                })
                .toArray(int[][]::new);

        int result = 1;
        for (int i = 1; i < points.length; i++) {
            if(points[i][0] > points[i-1][1]){
                result++;
            }else {
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }
        return result;
    }
}
